package Hot100;

import java.util.Arrays;

/**
 * @author zhangmin
 * @create 2022-01-06 21:06
 */
public class minMeetingRooms253 {

    /**
     * 253.会议室 II（中等）
     * 给你输入若干形如 [begin, end] 的区间，代表若干会议的开始时间和结束时间，请你计算至少需要申请多少间会议室。
     * 思路：计算最多有几个重叠区间，将所有区间投影到一条线上，从开始到结束，扫描，遇到起点+1，遇到终点-1
     * */
    int minMeetingRooms(int[][] meetings){
        int n=meetings.length;
        int[] begin=new int[n],end=new int[n];
        for (int i = 0; i < n; i++) {
            begin[i]=meetings[i][0];
            end[i]=meetings[i][1];
        }
        Arrays.sort(begin);
        Arrays.sort(end);
        int i=0,j=0,count=0,res=0;
        while (i<n&&j<n){
            if (begin[i]<end[i]){
                //遇到一个开始
                count++;
                i++;
            }else {
                count--;
                j++;
            }
            res=Math.max(res,count);
        }
        return res;
    }
}
